The present invention relates to a method of iteratively decoding product codes. The invention also relates to a transmission method and a transmission system using a decoding method of this kind.
The invention relates to decoding product codes of block linear codes. It applies to the field of channel coding for transmission. A typical transmission channel comprises a binary source, a coder, a modulator which transmits on a channel, a demodulator at the output of the channel, and a decoder which supplies the binary signal. The purpose of channel coding is to reduce the power needed to achieve a given bit error rate. French Patent Application No. 97 12594 filed on Oct. 9, 1997, whose title [in translation] is xe2x80x9cProduct code block coding method applicable in particular to coding an ATM cellxe2x80x9d, gives a description of the basic concepts of channel coding and transmission, and may be referred to for further details. To the degree that the invention relates to channel decoding, the other elements of the transmission systemxe2x80x94such as source coding and modulation to demodulation as a function of the transmission mediumxe2x80x94are not explained further.
It is conventional to use redundant codes and product codes for coding. A code C1 is generally characterized by a triplet (n1, k1, d1), where k1 is the number of input bits of the code, n1 is the number of output bits of the code and d1 is the minimum Hamming distance of the code. Applying a code of this kind to a k-tuplet (x1, . . . , xk) supplies an n-tuplet (x1, . . . , Xk, xk+1, . . . , xn) with nxe2x88x92k redundant bits.
The expression xe2x80x9cproduct codexe2x80x9d refers to the successive application of two codes C1 and C2, in the following manner. Consider k1.k2 bits, in the form of k2 words each of k1 bits. A code C1 (n1, k1, d1) is applied to the k2 words of k1 bits and k2 words of n1 bits are obtained. Stored in matrix form, the k2 words of n1 bits form n1 columns, the jth column being formed of the jth bit of each of k2 words. A code C2 (n2, k2, d2) is applied to each of these n1 columns of k2 bits to obtain n1 words of n2 bits. Applying a product code of the above kind changes from k1.k2 bits to n1.n2 bits, with n1.n2xe2x88x92k1.k2 redundant bits. If the codes are linear, this produces n2 rows of words of code C1 or n1 columns of words of code C2. The product code is a code having the parameters (n1.n2, k1.k2, d1.d2). The encoding order is immaterial, and the same results are obtained by coding the rows first, as described above, or by coding the columns first. Product codes of the above kind are described in the literature on channel coding. The French application referred to above and FIG. 2 of FR-A-2 712 760 explain in detail the principle of coding by means of a product code of the above kind.
The problem with product codes of the above kind is decoding at the demodulator output. Sets of values of bits (generally modulated in the form xc2x11) are obtained at the output of the demodulator, accompanied by noise. The value received, accompanied by noise, which is a real value, is referred to as a xe2x80x9csoftxe2x80x9d value. The value xc2x11, i.e. the corresponding binary value, obtained for a threshold-based decision on the value received is referred to as a xe2x80x9cfirmxe2x80x9d value. Hereinafter the expression xe2x80x9cfirm wordxe2x80x9d means a binary word and the expression xe2x80x9csoft wordxe2x80x9d means a word actually received, formed of real values.
On transmission with coding by a product code, a set R={ri,j} of n1.n2 real values (soft values) is obtained at the output of the demodulator. Decoding consists in determining the word of the product code C1.C2 to which the soft values correspond, according to some particular performance criterion. If the noise is additive Gaussian white noise, the optimum solution is to look for the product code word which minimizes the euclidean distance to the received soft word R. This criterion of the maximum likelihood is impossible in practice, once the product k1.k2 routinely exceeds a few hundred.
Various solutions have therefore been proposed to the problem of decoding product codes. The most immediate solution consists in taking firm decisions on each bit of the received soft word and successively decoding the rows and then the columns, as firm decisions, by applying a decoder of the code C2 to the columns and then a decoder of the code C1 to the rows. This solution is a long way short of the optimum and cannot achieve the theoretical gain of a product code because it does not use all the information received from the transmission channel.
FR-A-2 712 760 proposes an algorithm for iterative decoding of product codes C1.C2 in which the columns or rows of the matrix formed from the received product code word are decoded iteratively and successively. For each column or row, i.e. for each word of the code C2 or C1 received accompanied by noise (received soft word), the above document proposes to use a modified Chase algorithm for decoding, to be more precise:
generating a set of firm words of the code C2 or C1 a priori close to the received soft word in the corresponding row or column,
calculating the Euclidean distance between the various firm words and the received soft word, and
choosing as the received code word whichever of the various firm words is at the minimum distance from the soft word actually received.
To generate the set of firm words of the code C2 (or C1) a priori close to the received soft word, the above document proposes:
to mark the least reliable p components of the soft word received,
to construct q test binary sequences from the p least reliable components,
to construct q binary words to be decoded from the above sequences of binary tests and a current binary value of the decoded word, which current binary value is initialized at the outset by a binary approximation of each of the received bits, and
to decode the q binary words with a Berkelamp decoder (algebraic decoder) to obtain qxe2x80x2 code words, and if necessary to verify that the qxe2x80x2 words obtained are words of the code C2 (or C1).
The construction of the a binary words and their decoding by the above algorithm is inefficient: the q words generated are words of the code C2 (or C1), but are not necessarily different. There is obtained at the output of the decoder a number qxe2x80x2 of different code words which is less than the number q of words generated.
Also, the above method works only with codes for which there exists an algebraic decoder. Implementing algebraic decoders necessitates calculations in the Gallois body and a complex architecture.
A doctoral thesis submitted to the Paris ENST by Juing Fang in 1986, whose title [in translation] is xe2x80x9cWeighted decoding of block linear codesxe2x80x9d, describes a soft input algorithm for decoding a block linear code. The algorithm is optimum in the maximum likelihood sense and does not explicitly use the algebraic structure of the code. It supplies at the output a firm code word with maximum likelihood. The algorithm is one of many soft input to firm output decoding algorithms and there is no suggestion of using lists to generate a soft output.
The invention proposes a solution to the problem of iterative decoding of product codes which enables faster and more efficient decoding and which applies to all types of code, not only those for which there is an algebraic decoder.
Decoding product codes is not a mathematical problem, but rather a serious technical problem in the transmission field. It is applied directly to decoding values of received product code words or bits at the output of the demodulator of a transmission channel.
To be more precise, the invention proposes a method of soft input to soft output decoding of a word (s) of a block linear code of dimension k and length n, received from a transmission channel, comprising the steps of:
generating a list of firm words (ub) of the code close to the received code word (s) by coding a list of the most likely seeming k-tuplets, and
calculating the jth component of the output soft word as the difference between the metrics of the closest generated code word and the closest generated code word having an opposite jth component.
In one embodiment of the invention, the most likely k-tuplets are obtained by firm approximation of the components of the received word and by changing the least reliable components.
Each k-tuplet from the list of k-tuplets is advantageously obtained by:
listing the components of the received code word in order of reliability with a permutation (T),
verifying that the k most reliable components of the word obtained in this way can generate the other nxe2x88x92k components,
choosing firm values for the least reliable m components from said k components, where m is an integer less than k,
firmly approximating the other kxe2x88x92m components, and
coding the firm word obtained in this way by a code equal to the composition of said code by the inverse of said permutation.
The verification can also be effected by:
applying the code of the permutation to the columns of the parity matrix, and
verifying the rank of the matrix formed of the last nxe2x88x92k columns of the permutated parity matrix.
The verification step, when negative, is followed by a step of modifying the permutation.
In another embodiment of the invention each k-tuplet from the list of k-tuplets is obtained by:
listing the first k components of the received code word in order of reliability with a permutation (T),
choosing firm values for the least reliable m components, where m is an integer less than k,
firmly approximating the other kxe2x88x92m components, and
coding the firm word obtained in this way by a code equal to the composition of said code by the inverse of said permutation.
If there is no closest generated code word having an opposite jth component, the jth component of the output soft word is preferably calculated as the difference between the metric of the closest generated code word and the farthest generated code word.
If there is no closest generated code word having an opposite jth component, the jth component of the output soft word can also be calculated by adding to the jth component of the received word a coefficient assigned the sign of the firm decision of the jth component of the closest code word received.
The received word is advantageously affected by additive Gaussian white noise.
The invention also consists in a method of soft input to soft output decoding a word (s) of a block linear code of dimension k and length n received from a transmission channel, comprising the steps of:
choosing the code word closest the received word in a list of firm words (ub) of the code close to the received code word (s) generated by coding a list of the least likely k-tuplets,
for each jth component of the received word, j varying from 1 to n:
replacing the jth component of the received word by the inverse of the jth component of said nearest code word,
choosing the code word nearest the word obtained in the replacement step in a list of firm words of the code close to the code word obtained in the replacement step, generated by coding a list of the most likely k-tuplets,
calculating the jth component of the output soft word as the difference between the metric of the code word nearest the received word and the code word nearest the word obtained in the replacement step.
In one embodiment of the invention the step of choosing the code word closest to the received word the most likely k-tuplets are obtained by firmly approximating the most reliable components of the received word and changing the least reliable components.
In the step of choosing the code word closest to the word obtained in the replacement step the most likely k-tuplets are preferably obtained by firmly approximating the most reliable components of the word obtained in the replacement step and changing the least reliable components.
In one embodiment of the invention the received word is affected by additive Gaussian white noise.
The invention also consists in a method of iterative decoding a word (R) of a product code received from a transmission channel, comprising for at least one iteration soft input to soft output decoding of rows or columns of said product code word using a method of the above kind.